1. Field of the Invention
This invention is related to the field of microprocessors, and more particularly, to scheduling operations for execution in a microprocessor.
2. Description of the Related Art
Superscalar microprocessors achieve high performance by executing multiple instructions concurrently and by using the shortest possible clock cycle consistent with their design. However, data and control flow dependencies between instructions may limit how many instructions may be issued at any given time. As a result, some microprocessors support speculative execution in order to achieve additional performance gains.
One type of speculation is control flow speculation. Control flow speculation predicts the direction in which program control will proceed. For example, branch prediction may be used to predict whether a branch will be taken. Many types of branch prediction are available, ranging from methods that simply make the same prediction each time to those that maintain sophisticated histories of the previous branches in the program in order to make a history-based prediction. Branch prediction may be facilitated through hardware optimizations, compiler optimizations, or both. Based on the prediction provided by the branch prediction mechanism, instructions may be speculatively fetched and executed. When the branch instruction is finally evaluated, the branch prediction can be verified. If the prediction was incorrect, any instructions that were speculatively executed based on the incorrect predication may be quashed.
Another type of speculation is data speculation, which predicts data values. Some data speculation involves predicting the value that will be provided in response to a load instruction. This may be done by tracking the values that are stored in response to store instructions and, if a subsequent load uses the same register and/or displacement to specify an address as one of the previous stores used, speculatively using the value that was stored earlier. Another type of data speculation, value prediction, predicts the value of data items. Value prediction may involve observing patterns in data and basing the prediction on those patterns. For example, an index counter variable's value may be predicted by observing how prior values of that variable are incremented or decremented.
Another type of data speculation is address prediction, which involves predicting the location of data. Yet another type of data speculation is called memory system optimism. In multi-processor systems, memory system optimism occurs when a processor speculatively executes an instruction using data from that processor's local cache before coherency checking is complete. Similarly, another type of data speculation may allow a load to speculatively execute before a store that has an uncomputed address at the time the load executes, even though the store may store data to the same address that the load accesses. In all of these types of data speculation, the underlying conditions are eventually evaluated, allowing the speculation to be verified or undone. If the speculation ends up being incorrect, the instructions that executed using the speculative data may be re-executed (e.g., with updated and/or non-speculative data).
Since speculation allows execution to proceed without waiting for dependency checking to complete, significant performance gains may be achieved if the performance gained from correct speculations exceeds the performance lost to incorrect speculations. When a speculation turns out to be incorrect, the speculatively executed instructions are undone and execution is restarted non-speculatively. In order to undo speculative execution, each speculation may be recorded so that speculatively executed instructions can be identified in case the speculation turns out to be mispredicted.
One consequence of speculative execution is that schedulers (scheduling devices such as schedulers and reservation stations are collectively referred to as “schedulers” throughout) may not be able to deallocate speculative operations after execution, since these operations will need to be reissued if the underlying speculation is incorrect. A determination as to whether the underlying speculation is correct may not be made for several cycles, and it may not be possible to determine how many cycles it will take for that determination to be made. This uncertainty may make it difficult to ascertain when an operation can be deallocated from a scheduler. As a result, a scheduler entry may remain allocated to a speculative operation longer than is needed, leading to wasted space in the scheduler.